package projects;

import java.util.ArrayList;
import java.util.Random;


public class InstanceBasedLearner extends SupervisedLearner {

	public void train(Matrix features, Matrix labels) throws Exception {
		
		m_features = new Matrix(features, 0, 0, features.rows(), features.cols());
		m_labels = new Matrix(labels, 0, 0, labels.rows(), labels.cols());		
		int tenPercentOriginalData = m_features.rows() / 10;		
		
		m_valFeatures = saveValidationFeatures(m_features);
		m_valLabels = saveValidationFeatures(m_labels);
		m_features = nonValidationFeatures(m_features);
		m_labels = nonValidationFeatures(m_labels);			
		
		m_test = new Matrix();
		m_test.loadArff("input/housing-test.arff");
//		m_test.loadArff("input/mt_test.arff");
		m_test.normalize();
		
		testFeatures = new Matrix(m_test, 0, 0, m_test.rows(), m_test.cols() - 1);
		testLabels = new Matrix(m_test, 0, m_test.cols() - 1, m_test.rows(), 1);
		
//		double valAccuracy = measureAccuracy(m_valFeatures, m_valLabels, null);
//		System.out.println("valRows: " + m_features.rows() + "\taccuracy: " + valAccuracy);
//		
//		double testAccuracy = measureAccuracy(testFeatures, testLabels, null);
//		System.out.println("testRows: " + m_test.rows() + "\taccuracy: " + testAccuracy);

//		double mse = meanSquaredError(true);
//		System.out.println("valRows: " + m_valFeatures.rows() + "\tval-MSE: " + mse);
//		
//		mse = meanSquaredError(false);
//		System.out.println("testRows: " + m_features.rows() + "\ttest-MSE: " + mse);		

		testSet = false;
		if (reduceFeatures)
			while(m_features.rows() > tenPercentOriginalData)
				reduceFeatures();
	}	
	
	public void reduceFeatures() {
		
		Matrix reducedFeatures = new Matrix();
		Matrix reducedLabels = new Matrix();
		
		reducedFeatures = new Matrix(m_features, 0, 0, 
				m_features.rows(), m_features.cols());
		reducedLabels = new Matrix(m_labels, 0, 0, 
				m_labels.rows(), m_labels.cols());
		ArrayList<Integer> rowsToRemove = new ArrayList<Integer>();		
		for (int r = 0; r < m_features.rows(); r++)
			if (isAccurateWithout(r))
				rowsToRemove.add(r);
			
		for (Integer r : rowsToRemove) {
			reducedFeatures = removeRow(r, reducedFeatures);
			reducedLabels = removeRow(r, reducedLabels);				
		}		
		m_features = new Matrix(reducedFeatures, 0, 0, 
				reducedFeatures.rows(), reducedFeatures.cols());
		m_labels = new Matrix(reducedLabels, 0, 0, 
				reducedLabels.rows(), reducedLabels.cols());
		
		try {
//			double valAccuracy = measureAccuracy(m_valFeatures, m_valLabels, null);
//			System.out.println("valRows: " + m_features.rows() + "\taccuracy: " + valAccuracy);
//			
//			double testAccuracy = measureAccuracy(testFeatures, testLabels, null);
//			System.out.println("testRows: " + m_test.rows() + "\taccuracy: " + testAccuracy);
		}
		catch(Exception e) { e.printStackTrace(); }
		
		double mse = meanSquaredError(true);
		System.out.println("valRows: " + m_valFeatures.rows() + "\tval-MSE: " + mse);
		
		mse = meanSquaredError(false);
		System.out.println("testRows: " + m_features.rows() + "\ttest-MSE: " + mse);		
	}
	
	public double meanSquaredError(boolean valSet) {
		double sumSquaredError = 0.0;
		int max = valSet? m_valFeatures.rows() : testFeatures.rows();
		for (int r = 0; r < max; r++) {
			double[] query = valSet? m_valFeatures.row(r) : testFeatures.row(r);
			double[][] kNearestFeatures = kNearest(query, m_features, null);
			double[][] kNearestLabels = kNearest(query, m_features, m_labels);
			double prediction = predictLabel(query, kNearestFeatures, kNearestLabels);
			double actual = valSet? m_valLabels.get(r, 0) : testLabels.get(r, 0);
			sumSquaredError += Math.pow(prediction - actual, 2);			
		}
		double numRows = valSet? m_valFeatures.rows() : testFeatures.rows();
		double meanSquaredError = sumSquaredError / numRows;
		return meanSquaredError;
	}
		
	public boolean isAccurateWithout(int row) {
		
		Matrix m_featuresCopy = new Matrix(m_features, 0, 0, 
				m_features.rows(), m_features.cols());
		Matrix m_labelsCopy = new Matrix(m_labels, 0, 0, 
				m_labels.rows(), m_labels.cols());
		
		m_featuresCopy = removeRow(row, m_featuresCopy);
		m_labelsCopy = removeRow(row, m_labelsCopy);
		
		double[] features = m_features.row(row);
		double[][] kNearestFeatures = kNearest(features, m_featuresCopy, null);
		double[][] kNearestLabels = kNearest(features, m_featuresCopy, m_labelsCopy);
		double prediction = predictLabel(features, kNearestFeatures, kNearestLabels);		
		
		if (regressionMode) {
			double error = Math.abs(prediction - m_labels.get(row, 0));
			return (error < .11);
		}
		else
			return (prediction == m_labels.get(row, 0));
	}
	
	public void predict(int row, final double[] features, 
			double[] labels) throws Exception {
		
		if (row == 0 && count++ != 0)
			testSet = true;
		
		double[][] kNearestFeatures = kNearest(features, m_features, null);
		double[][] kNearestLabels = kNearest(features, m_features, m_labels);

		double prediction = predictLabel(features, kNearestFeatures, kNearestLabels);		
		if (testSet && regressionMode) {
			double actual = m_test.get(row, m_test.cols() - 1);
			sumSquaredError += Math.pow(prediction - actual, 2);
		}	
		if (testSet && row == m_test.rows() - 1 && regressionMode) {
			double meanSquaredError = sumSquaredError / m_test.rows();
			System.out.println("meanSquaredError: " + meanSquaredError);
		}
		labels[0] = prediction;
	}
	
	public double predictLabel(final double[] query, final double[][] features,
			final double[][] labels) {
		
		if (regressionMode) {
			double numerator = 0.0;
			double denominator = 0.0;
			for (int r = 0; r < labels.length; r++) {
				numerator += weight(query, features[r]) * labels[r][0];
				denominator += weight(query, features[r]);						
			}
			double quotient = numerator / denominator;
			return quotient;
		}
		else {
			int[] counts = new int[m_labels.valueCount(0)];
			for (int r = 0; r < labels.length; r++)
				counts[(int)labels[r][0]] += weight(query, features[r]);
			int maxIndex = 0;
			int maxValue = 0;
			for (int r = 0; r < counts.length; r++)
				if (counts[r] > maxValue) {
					maxValue = counts[r];
					maxIndex = r;
				}
			return maxIndex;
		}
	}
	
	public double weight(final double[] vector1, final double[] vector2) {
		if (!weightFeatures)
			return 1.0;
		else if (distance(vector1, vector2) == 0) 
			return m_labels.columnMax(0); // With normalization, this always returns 1.0
		else 
			return (double)1.0 / (double)Math.pow(distance(vector1, vector2), 2);
	}
		
	public double[][] kNearest(final double[] query, final Matrix features, final Matrix labels) {		
		int[] minDistanceRows = minDistanceRows(query, features);
		double[][] kNearest = new double[k][];
		for (int i = 0; i < k; i++) {
			double[] row = (labels == null)? features.row(minDistanceRows[i]) : 
				labels.row(minDistanceRows[i]);
			kNearest[i] = row;
		}
		return kNearest;
	}
	
	public int[] minDistanceRows(final double[] query, final Matrix matrix) {
		double[] distances = new double[matrix.rows()];
		for (int i = 0; i < matrix.rows(); i++)
			distances[i] = (distance(matrix.row(i), query));
		int[] minKRows = new int[k];
		for (int kNum = 0; kNum < k; kNum++) {
			double minValue = Double.MAX_VALUE;
			for (int i = 0; i < distances.length; i++) {
				if (distances[i] < minValue) {
					minValue = distances[i];
					minKRows[kNum] = i;
					distances[i] = Double.MAX_VALUE;
					assert(minValue != distances[i]);
				}
			}
		}
		return minKRows;
	}

	public double distance(final double[] vector1, final double[] vector2) {
		double sum = 0;
		for (int i = 0; i < vector1.length; i++)
			sum += Math.pow(vector1[i] - vector2[i], 2);
		return Math.sqrt(sum);
	}	
	
	public Matrix removeRow(int row, final Matrix matrix) {
		if (row >= matrix.rows())
			return matrix;
		Matrix newMatrix = new Matrix();
		try {
			assert(matrix.row(0) != null);
			newMatrix = new Matrix(matrix, 0, 0, row, matrix.cols());
			newMatrix.add(matrix, row + 1, 0, matrix.rows() - row - 1);
		} 
		catch(Exception e) { e.printStackTrace(); }
		return newMatrix;
	}

	public void print2DArray(String name, final double[][] array) {
		System.out.println(name + ":");
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				System.out.print(array[i][j] + "\t");
			}
			System.out.println();
		}
	}

	public void printArray(String name, final double[] array) {
		System.out.println(name + ":");
		for (int i = 0; i < array.length; i++)
			System.out.println(array[i]);
	}
	
	public static Matrix saveValidationFeatures(Matrix features) {
		Random rand = new Random(1);
		features.shuffle(rand);
		Matrix valFeatures = new Matrix(features, 0, 0, features.rows() / 5, features.cols());
		return valFeatures;
	}
	
	public static Matrix nonValidationFeatures(Matrix features) {
		Random rand = new Random(1);
		features.shuffle(rand);
		Matrix nonValFeatures = new Matrix(features, features.rows() / 5, 0, 
				features.rows() - features.rows() / 5, features.cols());
		return nonValFeatures;
	}	

	private Matrix testFeatures;
	private Matrix testLabels;
	private Matrix m_features;
	private Matrix m_labels;
	private Matrix m_test;
	private Matrix m_valFeatures;
	private Matrix m_valLabels;
	private boolean testSet;
	private int count;
	private double sumSquaredError = 0.0;
	private final boolean weightFeatures = false;
	private final boolean regressionMode = false;
	private final boolean reduceFeatures = false;
	private final int k = 7;
}
